#include"queue.hpp"

BTNode* CreateTree()
{
  BTNode* root =  (BTNode*)malloc(sizeof(BTNode));
  BTNode* node2 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node4 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node3 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node5 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node6 = (BTNode*)malloc(sizeof(BTNode));

  root->data = 1;
  node4->data =4;
  node3->data =3;
  node5->data =5;
  node6->data =6;
  node2->data =2;
  
  root->left = node2;
  root->right = node4;
  node2->left = node3;
  node2->right = NULL;
  node3->left = NULL;
  node3->right = NULL;
  node4->left = node5;
  node4->right = node6;
  node6->left = NULL;
  node6->right = NULL;
  node5->left = NULL;
  node5->right = NULL;
  return root;
}
//前序遍历
void BinaryPrev(BTNode* root)
{
  if(root==NULL) {printf("NULL ");return;}
  printf("%d  ",root->data);
  BinaryPrev(root->left);
  BinaryPrev(root->right);
}
//中序遍历
void BinaryIn(BTNode* root)
{
  if(root==NULL) {printf("NULL ");return;}
  BinaryIn(root->left);
  printf("%d  ",root->data);
  BinaryIn(root->right);
}
//后序遍历
void BinaryPost(BTNode* root)
{
  if(root==NULL) {printf("NULL ");return;}
  BinaryPost(root->left);
  BinaryPost(root->right);
  printf("%d  ",root->data);
}
//层序遍历
void BinaryLevel(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if(root!=NULL)
  {
     QueuePush(&q,root);
  }
  while(!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    printf("%d  ",front->data);
    if(front->left)
    QueuePush(&q,front->left);
    if(front->right)
    QueuePush(&q,front->right);
    QueuePop(&q);
  }
  QueueDestory(&q);
}
//节点个数
int BinaryTreeSize(BTNode* root)
{
  return root==NULL?0:BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
//叶子节点个数
int BinaryTreeLeaf(BTNode* root)
{
  if(root==NULL) return 0;
  if(root->left==NULL&&root->right==NULL) return 1;
   
   return BinaryTreeLeaf(root->left)+BinaryTreeLeaf(root->right);
}

//第k层节点数
int BinaryTreeLeveSize(BTNode* root,int k)
{
  if(root==NULL||k<1)  return 0;
  if(k==1) return 1;
  return BinaryTreeLeveSize(root->left,k-1)+BinaryTreeLeveSize(root->right,k-1);

}

//寻找值为x的节点
BTNode* BinaryFind(BTNode* root,BTDataType x)
{
  if(root==NULL) return NULL;
  if(root->data==x)  return root;

  BTNode* lret = BinaryFind(root->left,x);
  if(lret)  return lret;
  BTNode* rret = BinaryFind(root->right,x);
  if(rret) return rret;

  return NULL;
}

//求较大值
int Max(int a, int b)
{
return a > b ? a : b;
}
 
//树的深度
int TreeDep(BTNode* root)
{
  if(root==NULL) return 0;
  return Max(TreeDep(root->left),TreeDep(root->right))+1;
}
//反转二叉树
BTNode* inverTree(BTNode* root)
{
  if(root==NULL) return NULL;
  BTNode* left = inverTree(root->left);
  BTNode* right = inverTree(root->right);

  root->left = right;
  root->right = left;

  return root;
}

//判断二叉树是否相同
bool IsSameTree(BTNode* p,BTNode* q)
{
  if(p==NULL&&q==NULL) return true;
  if(p==NULL||q==NULL) return false;

  if(p->data!=q->data) return false;

  return IsSameTree(p->left,q->left)&&IsSameTree(p->right,q->right);
}

//判断二叉树是否是完全二叉树
bool isCompleteTree(BTNode* root)
{
  Queue q;
  QueueInit(&q);//初始化队列
  if(root!=NULL)
    QueuePush(&q,root);
  while(!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if(front==NULL)
    {
      break;
    }
    QueuePush(&q,front->left);
    QueuePush(&q,front->right);
  }

  while(!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if(front!=NULL)
    {
      QueueDestory(&q);
      return false;
    }
  }
  QueueDestory(&q);
  return true;
}
//判断是否是单值二叉树
bool isUnival(BTNode* root)
{
  if(root==NULL) return true;
  if(root->left&&root->left->data!=root->data) return false;
  if(root->right&&root->right->data!=root->data) return false;
  return isUnival(root->left)&&isUnival(root->right);
}
//判断是否是对称二叉树
bool travel(BTNode* left,BTNode* right)
{
  if(left==NULL&&right==NULL) return true;
  if(left==NULL || right==NULL) return false;
  if(left->data!=right->data) return false;

  return travel(left->left,right->right)&&travel(left->right,right->left);
}


bool isSymmetric(BTNode* root)
{
  if(root==NULL) return true;
  return travel(root->left,root->right);
}

//判断是否是平衡二叉树
bool isBalanced(BTNode* root)
{
  if(root==NULL) return true;
  int leftd = TreeDep(root->left);
  int rightd =TreeDep(root->right); 

  return abs(leftd-rightd)<2&&isBalanced(root->left)&&isBalanced(root->right);
}
//判断是否是子树
bool IsCompare(BTNode* root,BTNode* subRoot)
{
  if(root==NULL&&subRoot==NULL)
    return true;
  if(root==NULL||subRoot==NULL)
    return false;
  if(root->data!=subRoot->data) return false;
  //比较下面的节点
  return IsCompare(root->left,subRoot->left)&&IsCompare(root->right,subRoot->right);
}

bool isSubTree(BTNode* root,BTNode* subRoot)
{
  if(root==NULL) return false;
  if(IsCompare(root,subRoot)) return true;
  return isSubTree(root->left,subRoot)||isSubTree(root->right,subRoot);
}

//二叉树销毁
void BinaryDestory(BTNode* root)
{
  if(root==NULL) return ;
  BinaryDestory(root->left);
  BinaryDestory(root->right);
  free(root);
}
//二叉树前序遍历存在数组，返回数组

void Preorder(BTNode* root,int* arr,int* pi)
{
  if(root==NULL) return ;
  arr[(*pi)++] = root->data; 
  Preorder(root->left,arr,pi);
  Preorder(root->right,arr,pi);
}

int* PreorderTravel(BTNode* root,int* returnSize)
{
  *returnSize = BinaryTreeSize(root);
  int* arr = (int*)malloc(sizeof(int)*(*returnSize));
  int i = 0;
  Preorder(root,arr,&i);
  return arr;
}
//中序遍历
void  inorder(BTNode* root,int* arr,int* pi)
{
  if(root==NULL) return ;
  inorder(root->left,arr,pi);
  arr[(*pi)++] = root->data; 
  inorder(root->right,arr,pi);
}

int* inorderTravel(BTNode* root,int* returnSize)
{
  *returnSize = BinaryTreeSize(root);
  int* arr = (int*)malloc(sizeof(int)*(*returnSize));
  int i = 0;
  inorder(root,arr,&i);
  return arr;
}
//后序遍历
void  postorder(BTNode* root,int* arr,int* pi)
{
 // if(root==NULL) return ;
 // inorder(root->left,arr,pi);
 // inorder(root->right,arr,pi);
 // arr[(*pi)++] = root->data;
 if (root == NULL)//根结点为空，直接返回
		return;
	postorder(root->left, arr, pi);//先将左子树中结点的值放入数组
	postorder(root->right, arr, pi);//再将右子树中结点的值放入数组
	arr[(*pi)++] = root->data;//最后将根结点的值放入数组
}

int* postorderTravel(BTNode* root,int* returnSize)
{
  *returnSize = BinaryTreeSize(root);
  int* arr = (int*)malloc(sizeof(int)*(*returnSize));
  int i = 0;
  postorder(root,arr,&i);
  return arr;
}

//根据前序遍历建立树
BTNode* CreateTreePre(char* str,int* pi)
{
  if(str[*pi]=='#')
  {
    (*pi)++;
    return NULL;
  }

  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  root->left = NULL;
  root->right = NULL;
  root->data = str[*pi];
  (*pi)++;

  root->left = CreateTreePre(str,pi);
  root->right = CreateTreePre(str,pi);

  return root;
}
int main()
{
  BTNode* root = CreateTree();
  BinaryPrev(root);
  printf("\n");
  BinaryIn(root);
  printf("\n");
  BinaryPost(root);
  printf("\n");
  BinaryLevel(root);
  printf("\n");
  printf("Size = %d\n",BinaryTreeSize(root));
  printf("LeafSize = %d\n",BinaryTreeLeaf(root));
  printf("LevelSize = %d\n",BinaryTreeLeveSize(root,3));
  BTNode* ret = BinaryFind(root,3);
  printf("Find:ret = %d\n",ret->data);
  printf("Tree Depth: %d\n",TreeDep(root));
  
  printf("完全二叉树：%d\n",isCompleteTree(root));
  printf("单值二叉树：%d\n",isUnival(root));
  printf("对称二叉树：%d\n",isSymmetric(root));
  printf("平衡二叉树：%d\n",isBalanced(root));
  int size = 0;
  int* arr = PreorderTravel(root,&size);
  int i=0;
  for(i=0;i<size;i++)
  {
    printf("%d  ",arr[i]);
  }
  printf("\n");
  arr = inorderTravel(root,&size);
  for(i=0;i<size;i++)
  {
    printf("%d  ",arr[i]);
  }
  printf("\n");
  arr = NULL;
  arr = postorderTravel(root,&size);
  for(i=0;i<size;i++)
  {
    printf("%d  ",arr[i]);
  }
  printf("\n");
  printf("输入字符串构建树\n");
  char str[100];
  scanf("%s",str);
  int j = 0;
  BTNode* tree = CreateTreePre(str,&j);
  BinaryPrev(tree);
  printf("\n");
  return 0;
}

